
import java.util.Arrays;
class Solution {
    //分发饼干
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int k = 0;
        for(int i = 0; i < s.length && k < g.length; i++){
            if(s[i] >= g[k]){
                k++;
            }
        }
        return k;
    }

    //最优除法
    public String optimalDivision(int[] nums) {
        StringBuilder ret = new StringBuilder();
        if(nums.length == 1){
            ret.append(nums[0]);
        }else if(nums.length == 2){
            ret.append(nums[0]).append("/").append(nums[1]);
        }else{
            ret.append(nums[0]).append("/").append("(");
            int i = 1;
            for(; i < nums.length - 1; i++){
                ret.append(nums[i]).append("/");
            }
            ret.append(nums[i]).append(")");
        }
        return ret.toString();
    }
    //跳跃游戏II
    public static int jump(int[] nums) {
        if(nums.length == 1) return 0;
        int left = 0, right = 0;//从第一个位置到最远位置
        int count = 0;
        while(right < nums.length){
            int newRight = right + 1;//下一跳最远区间
            for(int i = left; i <= right; i++){
                if(newRight < nums[i] + i) newRight = nums[i] + i;
            }
            count++;
            if(newRight >= nums.length - 1) break;
            left = right + 1;
            right = newRight;
        }
        return count;
    }
    //跳跃游戏
    public static boolean canJump(int[] nums) {
        if(nums.length == 1) return true;
        int left = 0, right = 0;
        while(left <= right){
            int newRight = right;
            for(int i = left; i <= right; i++){
                if(newRight < i + nums[i]) newRight = i + nums[i];
            }
            if(newRight >= nums.length - 1) return true;
            left = right + 1;
            right = newRight;
        }
        return false;
    }

    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};
        canJump(nums);
        jump(nums);
       // System.out.println(jump(nums));
    }
}